package com.mdnote.structure.sparse_array;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/10/8
 * @description 二分查找
 */
public class BinarySearch {


    public static void main(String[] args) {
        BinarySearch binarySearch = new BinarySearch();
        int b = binarySearch.right_bound(new int[]{1, 2, 2, 2, 3}, 2);
        System.out.println(b);
    }

    public boolean binary_search(int[] arr, int target ){
        int left = 0, right = arr.length - 1;   // 细节1
        while (left < right) {					// 细节2
            int mid = ((right - left) >> 1 ) + left;
            if (arr[mid] == target) {
                return true;
            } else if (arr[mid] > target) {
                right = mid - 1;				// 细节3
            } else if (arr[mid] < target) {
                left = mid + 1;					// 细节3
            }
        }
        return arr[left] == target;
    }

    public int left_bound(int[] arr, int target) {
        int left = 0, right = arr.length;
        while (left < right) {
            int mid = ((right - left) >> 1) + left;
            if (arr[mid] == target) {
                right = mid;
            } else if (arr[mid] > target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        // left == right，
        if (left == arr.length) {
            return -1;
        }
        return arr[left] == target ? left : -1;
    }

    private int right_bound(int[] arr, int target) {
        int left = 0, right = arr.length;
        while (left < right) {
            int mid = ((right - left) >> 1) + left;
            if (arr[mid] == target) {
                left = mid + 1;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        // left = right, 如果数组中有目标值 left会停在target的下一个元素的位置
        //               如果目标值比数组所有的值大，    right = left = nums.length
        //               如果目标值比数组中的值都小      left = right = 0
        if (left == 0) {
            return  -1;
        }

        return arr[left - 1] == target ? left - 1 : - 1;
    }
}
